COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	warpla[w85,jmc]		Notes on David Warren's WARPLAN
C00010 ENDMK
C⊗;
warpla[w85,jmc]		Notes on David Warren's WARPLAN

See also strips[w85,jmc]

WARPLAN: A System for Generating Plans, University of Edinburgh,
School of Artificial Intelligence, Memo Number 76

Special axioms for block stacking:

+ add ( on(U,W), move(U,V,W))
Note: the + means a postive literal in the Prolog disjunction.
The axiom means that  on(U,W) is added to the database when  U
is moved from  V  to  W.

+ add(clear(V),move(U,V,W)) ; this clears V

+ del(on(U,Z), move(U,V,W)) ; since there will be but one on(U,Z),
there will be no question of whether one is deleted or all are.

+ del(clear(W),move(U,V,W))

Note that the order of these precondition clauses is essential
and relies on Prolog's ordering.  The corresponding statements
in logic will be somewhat more complicated.
+ can(move(U,V,floor), on(U,V) & V ≠ floor & clear(U)).

+ can(move(U,V,W),clear(W)&on(U,V) & U ≠ W & clear(U)).; why not also V ≠ W?

+ imposs(on(X,Y) & clear(Y))
+ imposs(on(X,Y) & on(X,Z) & Y ≠ Z).
+ imposs(on(X,X)).

The particular situation for the five block problem is given by

+ given(start, on(a,floor)).
+ given(start, on(b,floor)).
+ given(start, on(c,a)).
+ given(start, on(d,floor)).
+ given(start, on(e,d)).
+ given(start, clear(b)).
+ given(start, clear(c)).
+ given(start, clear(e)).

Note that what is clear is explicitly listed.

The problem of stacking all five blocks is then given by

- plans(on(a,b) & on(b,c) & on(c,d) & on(d,e), start)

Notes:

clear(X) is updated, so it never has to be established using negation
as failure.

The big question:  How can we give the fact that towers are built from
the bottom up in as declarative a form as possible?  For humans, the
blocks problems are not arbitrary conjunctive goals.

Let's formulate it.  We can use  above(X,Y).  If  on(X,Y)  is goal, it
is pointless to achieve it as long as some  on(Y,Z)  is an unsatisfied
goal.  We might consider putting that into the preconditions for
move(X,V,Y), but it isn't a physical precondition.  Also it
will be appropriate only if  on(Y,Z) is a goal involved in building
the same tower for which we are trying to achieve  on(X,Y).  Thus we
may put  X  on  Y  in the Tower-of-Hanoi problem.  We must also
regard  on(Y,Z)  as unachieved even if it's true if the lower blocks
aren't in place.

	It looks like we may not need  above(X,Y),  but let's use
it anyway.  We want to say that  on(X,Y)  is inappropriate if there
holds  above(Y,Z)  and an unachieved  on(Z,W).

Remark: Looking at Warren's description on p.9 reminds me of postponability.
on(a,b)  needs to be postponed till  on(b,c)  is achieved.  However, in
this case, unlike in the map coloring problem, the Kowalski and Bowen
idea of selecting what goal to do first will work.  The bottoms of the
desired towers are the first goals.

The fact that towers should be built bottom up is a consequence of
a more general principle.  Namely, if we have a conjunct, it is pointless
to achieve one conjunct if it must be destroyed in achieving another.
Therefore, we can have an algorithm that selects a goal tentatively,
but postpones it past another goal if it discovers that achieving the
first goal directly spoils the other.  Hmm. There may be many ways of
achieving the first goal some of which won't spoil the second.  Note,
however, that putting the bottom block of a tower on the floor won't
spoil any other goal, so that's a safe way of proceeding.  However,
we can have problems in which there is some way of achieving each
goal that spoils other goals.

It would seem that keeping to WARPLAN's style, we could add an
operator  postpone  and write

+ postpone(on(U,W), above(W,Z) & goal(on(Z,X)) & not on(Z,X))

Perhaps we want to keep track of unsatisfied goals, labelling them
all initially unsatisfied.  We would have

+ postpone(on(U,W), above(W,Z) & unsatisfied(Z))

i.e.  Z  is not in its final position.

PEACEPLAN is a more powerful version of David Warren's WARPLAN.
Research supported by DoD.

The goal of PEACEPLAN is to find solutions by restricting the
deductions that can be made.  Reifying propositions will allow us
to make not all correct deductions but only those that obey
the strategy axioms.

Consider a system with an inner language and an outer language;
in general both are first order languages, but it is more convenient
to restrict the inner language in various ways.  For purposes of
illustration it can even be taken to be propositional.

For example, let the inner language be the language of propositional
Robinson clauses.  We have

db(c1 or p) ∧ db(not(p) or c2) ⊃ candeduce(c1 or c2)

...